package 从前序与中序遍历序列构造二叉树;

public class Solution {
    /*
    给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，
    inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 递归法
        // 递归参数：int[] preorder, preleft, preright, int[] inorder, inleft, inright
        // 递归返回值:返回当前创建的根节点
        // 递归终止条件：inleft >= inright 说明没有孩子节点了
        // 单层递归逻辑：根据preorder查询到根节点，然后在inorder中查找到当前的根节点。根据inorder确定根节点的左右子树
        // 最后需要确定左右子树的区间，严格遵守 “左闭右开” 原则。
        // 在preorder中，利用preleft，preright定义区间，在inorder中，利用inleft，inright定义区间
        // 当确定左子树时，需要传递上面四个参数，四个参数具体计算规则见代码。右子树同理,拆分为左根区间，跟右区间
        // 左子树根节点的区间：preleft+1 <--> preleft+len+1  左闭右开
        // 右子树根节点的区间： preleft+len+1 <--> preright 左闭右开
        if(preorder==null || inorder == null){
            return null;
        }
        TreeNode root = build(preorder, 0, preorder.length, inorder, 0, inorder.length);
        return root;
    }
    public TreeNode build(int[] preorder, int preleft, int preright, int[] inorder, int inleft, int inright) {
        // 终止条件
        if(preleft >= preright || inleft >= inright){
            return null;
        }
        // 确定根节点
        int value = preorder[preleft];
        // 找到根节点在inorder中的位置
        int index;
        for ( index= 0; index < inorder.length; index++) {
            if(value == inorder[index]){
                break;
            }
        }
        TreeNode root = new TreeNode(value);
        // 左子树的节点数， 用于确认preorder的左区间
        int len = index - inleft;
        // 构建左子树. 左子树根节点的区间：preleft+1 <--> preleft+len+1  左闭右开
        root.left = build(preorder, preleft+1, preleft+len+1,
                          inorder, inleft, index);
        // 构建右子树。右子树根节点的区间： preleft+len+1 <--> preright 左闭右开
        root.right = build(preorder, preleft+len+1, preright,
                            inorder,  index+1, inright);
        return root;
    }
}